167. 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组  numbers ，该数组已按 非递减顺序排列   ，请你从数组中找出满足相加之和等于目标数  target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

示例 1

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

答案

思路：通过 Map 进行

1. 防御性
2. 声明 map 对象
3. 遍历数组，计算差值
   • 不存在则存入 map
   • 存在则[下标]

哈希表

const twoSum = function (nums, target) {
  // 数组和数字直接返回
  if (Object.prototype.toString.call(nums) !== '[object Array]' || typeof target !== 'number') {
    return;
  }

  const map = new Map()

  for (let i = 0; i < nums.length; i++) {
      const result = target - nums[i];
      if (map.has(result)) {
        return [map.get(result)+1, i+1]
      }
      map.set(nums[i], i)
  }
};

双指针

const twoSum = function (nums, target) {
  if (Object.prototype.toString.call(nums) !== '[object Array]' || typeof target !== 'number') return;

  let low = 0;
      high = nums.length - 1;
  while (low < high) {
    let sum = nums[low] + nums[high];
    if (sum < target) {
      low ++
    } else if (sum > target) {
      high --
    } else {
      return [low+1, high+1]
    }
  }
};